﻿#define _CRT_SECURE_NO_WARNINGS

/*Eli最近迷上了汉诺塔。她玩了传统汉诺塔后突发奇想，发明了一种新的汉诺塔玩法。
有A、B、C三个柱子顺时针放置，移动的次序为A仅可以到B，B仅可以到C、C仅可以到A。即只可顺时针移动，不可逆时针移动。当然，汉诺塔的普适规则是适用的：每次移动后，大金片必须在小金片的下面。
现在A柱子上有
n
 
n 个金片。Eli想知道，她把这些全部移动到B或C，分别要多少次操作？*/


#include <iostream>
using namespace std;

const int m = 1e9 + 7;
const int N = 1e7 + 10;
int main() {
    int n;
    cin >> n;

    int x = 1, y = 2;
    for (int i = 2; i <= n; i++)
    {
        int xx = x, yy = y;
        x = (2 * yy + 1) % m;
        y = (2 * yy % m + 2 + xx) % m;
    }

    cout << x << " " << y;
}
// 64 位输出请用 printf("%lld")

/*链接：https://ac.nowcoder.com/acm/problem/50042
来源：牛客网

kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。

她想知道，最终所有取出的数的和的最小值是多少？*/

#include <iostream>
#include <cmath>
using namespace std;
const int N = 1010;
int ret = 0x3f3f3f3f, sum = 0;
bool vis[N] = { false };
int n;
int arr[15];
bool checknum(int x)
{
    if (x < 2)    return false;

    for (int i = 2; i <= sqrt(x); i++)
    {
        if (x % i == 0)    return false;
    }
    return true;
}
void dfs(int pos)
{
    if (pos == n + 1)
    {
        ret = min(ret, sum);
        return;
    }

    ;
    for (int i = 2; i <= arr[pos - 1]; i++)
    {

        if (!vis[i] && arr[pos - 1] % i == 0 && checknum(i))
        {
            sum += i;
            vis[i] = true;
            dfs(pos + 1);
            sum -= i;
            vis[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    dfs(1);
    if (ret == 0x3f3f3f3f)    cout << -1 << endl;
    else    cout << ret << endl;
    return 0;
}

/*现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向 或 在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。

给定一个地图 CityMap 及它的 行长度 n 和 列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。
注意：需保证所有方案的距离都是最短的方案*/


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param CityMap int整型vector<vector<>>
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    int ret = 0;

    bool vis[10][10];
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, 1, 0, 0 };
    void bfs(vector<vector<int> >& nums, int i, int j, int n, int m) {
        queue<pair<int, int>> q;
        q.push({ i, j });
        vis[i][j] = true;

        while (q.size()) {

            auto [x, y] = q.front();
            q.pop();

            if (nums[x][y] == 2) {
                ret++;
            }
            else {
                for (int k = 0; k < 4; k++) {
                    int a = x + dx[k], b = y + dy[k];
                    if (a >= 0 && a < n && b >= 0 && b < m && !vis[a][b] && nums[a][b] != -1) {
                        q.push({ a, b });
                    }
                }
            }
        }
    }
    int countPath(vector<vector<int> >& nums, int n, int m) {
        // write code here
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nums[i][j] == 1) {
                    bfs(nums, i, j, n, m);
                    return ret;
                }
            }
        }

        return 1;
    }
};

/*假设你有一个数组
p
r
i
c
e
s
prices，长度为
n
n，其中
p
r
i
c
e
s
[
i
]
prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你最多可以对该股票有
k
k笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费*/

#include <iostream>
using namespace std;

const int N = 1010;
int f[N][101];
int g[N][101];
int nums[N];
int main() {
    int n, k;
    cin >> n >> k;
    k = min(k, n / 2);
    for (int j = 0; j <= k; j++)   f[0][j] = g[0][j] = -0x3f3f3f3f;
    int x;
    cin >> x;
    f[0][0] = -x;
    g[0][0] = 0;
    for (int i = 1; i < n; i++)
    {
        int x; cin >> x;

        for (int j = 0; j <= k; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - x);
            g[i][j] = g[i - 1][j];
            if (j > 1)   g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + x);
        }
    }

    int ret = 0;
    for (int i = 0; i <= n; i++)    ret = max(ret, g[n - 1][i]);

    cout << ret << endl;
}

/*KiKi有一个矩阵，他想知道转置后的矩阵（将矩阵的行列互换得到的新矩阵称为转置矩阵），
请编程帮他解答。*/


#include <iostream>
using namespace std;
const int N = 15;

int nums[N][N];
int main() {
    int n, m; cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)    cin >> nums[i][j];
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << nums[j][i] << " ";
        }
        cout << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")

/*给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。*/

class Solution {
public:

    int left[20010];
    int right[20010];
    int trap(vector<int>& height) {
        int n = height.size();
        left[0] = height[0];
        for (int i = 1; i < n; i++)    left[i] = max(left[i - 1], height[i]);
        right[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) right[i] = max(right[i + 1], height[i]);
        int ret = 0;
        for (int i = 1; i < n - 1; i++)
        {
            ret += min(left[i], right[i]) - height[i];
        }

        return ret;
    }
};

/*链接：https://ac.nowcoder.com/acm/problem/224938
来源：牛客网

小红拿到了一个长度为 
𝑛
 
n  的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 
𝑘
 
k  次操作。她希望操作结束后，该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗？*/